package pro.softzhang.algo.lc400;

import pro.softzhang.algo.common.ListNode;
import pro.softzhang.algo.common.Utils;

/**
 * 输入：l1 = [7,2,4,3], l2 = [5,6,4]
 * 输出：[7,8,0,7]
 */
public class LC445_AddTwoNumbersII {
    public static void main(String[] args) {
//        ListNode l1 = new ListNode(7, new ListNode(2, new ListNode(4, new ListNode(3, null))));
//        ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
        ListNode l1 = new ListNode(5, null);
        ListNode l2 = new ListNode(5, null);
        ListNode r = new LC445_AddTwoNumbersII().addTwoNumbers(l1, l2);
        Utils.printLinkedList(r);
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverseList(l1); // 3 4 2 7
        l2 = reverseList(l2); // 4 6 5
        ListNode dummy = new ListNode(), current = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            if(l1 == null) {
                l1 = new ListNode(0, null);
            }
            if(l2 == null) {
                l2 = new ListNode(0, null);
            }
            int tmp = l1.val + l2.val + carry;
            carry = tmp / 10;
            ListNode ln = new ListNode(tmp % 10, null);
            current.next = ln;
            current = ln;
            l1 = l1.next;
            l2 = l2.next;
        }

        if(carry != 0) {
            current.next = new ListNode(carry, null);
        }

        return reverseList(dummy.next);
    }

    private ListNode reverseList(ListNode head) {
        ListNode previous = null, current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        return previous;
    }
}
